package com.zj.sixtyDayChallenge.tree;

import java.util.*;

/**
 * @program: algorithm
 * @description: 二叉树的前序遍历
 * 144 binary-tree-preorder-traversal
 * //给你二叉树的根节点 root ，返回它节点值的 前序 遍历。
 * //
 * //
 * //
 * // 示例 1：
 * //
 * //
 * //输入：root = [1,null,2,3]
 * //输出：[1,2,3]
 * //
 * //
 * // 示例 2：
 * //
 * //
 * //输入：root = []
 * //输出：[]
 * //
 * //
 * // 示例 3：
 * //
 * //
 * //输入：root = [1]
 * //输出：[1]
 * //
 * //
 * // 示例 4：
 * //
 * //
 * //输入：root = [1,2]
 * //输出：[1,2]
 * //
 * //
 * // 示例 5：
 * //
 * //
 * //输入：root = [1,null,2]
 * //输出：[1,2]
 * //
 * //
 * //
 * //
 * // 提示：
 * //
 * //
 * // 树中节点数目在范围 [0, 100] 内
 * // -100 <= Node.val <= 100
 * //
 * //
 * //
 * //
 * // 进阶：递归算法很简单，你可以通过迭代算法完成吗？
 * //
 * // Related Topics 栈 树 深度优先搜索 二叉树 👍 992 👎 0
 * @author: Zhang Bo
 * @create: 2022-01-14 17:05
 **/
public class BinaryTreePreorderTraversal {
    public static void main(String[] args) {
        Solution solution = new BinaryTreePreorderTraversal().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    class Solution {
        public List<Integer> preorderTraversal(TreeNode root) {

            if (root == null) {
                return new ArrayList<>();
            }

            Stack<TreeNode> queue = new Stack<>();
            queue.push(root);

            ArrayList<Integer> list = new ArrayList<>();
            while (!queue.isEmpty()) {

                TreeNode poll = queue.pop();
                list.add(poll.val);

                if(poll.right != null){
                    queue.push(poll.right);
                }

                if(poll.left != null){
                    queue.push(poll.left);
                }


            }
            return list;

        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}